import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Random;
import java.util.Set;

/**
 * http://community.topcoder.com/longcontest/?module=ViewProblemStatement&compid=31324&rd=15608
 * 
 * V13
 * 
 * @author smarsoll
 * 
 */
public class SnowCleaning {
	/** Differen algo considerations during last days. */
	private static final int LAST_DAYS = 1999;
	private static final int NB_MAX_WORKERS = Const.MAX_WORKERS;
	private static final int MAX_BEST_TARGET_EVAL = 1000;
	/** maximum distance to consider snow as not to be targeted again, 6. */
	private static final int MAX_DIST = 6;
	/** maximum difference to keep a target (with an other working worker) 9 is good. */
	private int MAX_DIFFERENCE = 9;
	int boardSize;
	int salary;
	int snowFine;
	/** nb tot worker by day since begining. */
	int nbWorkersByDay = 0;
	int snowFallSinceStart = 0;
	Board world;

	/** 100 added to snow probabilty. */
	private static final int BASE_SNOW_PROBABILITY = 100;
	/** store past snow probability. */
	int[][] snowProba;

	CellW maxPos = new CellW(0, 0);
	CellW minPos = new CellW(0, 0);
	CellW minPos2 = new CellW(0, 0);
	// for test use new Random(7) or 37
	private Random rnd = new Random(37);
	private int nbWorkersBeforeTurn;

	/**
	 * init will be called only once and before all nextDay calls. It serves to give your solution the values of
	 * boardSize, salary and snowFine. The return value from this method will be ignored.
	 * 
	 * @param boardSize
	 * @param salary
	 * @param snowFine
	 * @return
	 */
	public int init(int boardSize, int salary, int snowFine) {
		this.boardSize = boardSize;
		this.salary = salary;
		this.snowFine = snowFine;
		this.world = new Board(boardSize, salary, snowFine);
		snowProba = new int[boardSize][boardSize];
		// MAX_DIFFERENCE = 10 * boardSize / 35;
		return 0;
	}

	/**
	 * nextDay will be called 2,000 times -- once for each day. Its input parameter snowFalls contains exactly 2*K
	 * elements where K is the number of snowfalls at this day. The elements are Row[0], Col[0], Row[1], Col[1], ...,
	 * Row[K-1], Col[K-1], respectively
	 * 
	 * @param snowFalls
	 * @return
	 */
	public String[] nextDay(int[] snowFalls) {
		world.startNewDay();
		ArrayList<String> command = new ArrayList<String>();
		final int k = snowFalls.length / 2;
		// log("day=" + world.curDay + " k=" + k);
		snowFallSinceStart += k;
		// store snow information
		for (int i = 0; i < k; i++) {
			int row = snowFalls[2 * i];
			int col = snowFalls[2 * i + 1];
			world.addSnow(row, col);
		}

		nbWorkersBeforeTurn = world.workers.size();
		initMinMax(world.workers);

		// list of cells with snow that are targeted.
		// HashSet has better score than TreeSet
		Set<CellW> snowNoWorker = new HashSet<CellW>(world.cellsWithSnow);
		// snowNoWorker.removeAll(world.workers);

		// snow inside a cloud (no need to be targeted)
		final Set<CellW> snow4Borders = getSnow4Borders(snowNoWorker);
		if (snow4Borders.size() > 0) {
			// remove where there is a worker ?
			// log("snow4Borders.size()=" + snow4Borders.size());
			// ignor them not to target them
			snowNoWorker.removeAll(snow4Borders);
		}

		// workers without snow or target work
		final List<CellW> freeWorker = new ArrayList<CellW>(world.workers);
		// freeWorker.removeAll(world.cellsWithSnow);

		// position for workers next turn: we keep the one already at good place
		final Collection<CellW> nextTurnWorkers = new ArrayList<CellW>(100);
		// new HashSet<CellW>(world.cellsWithSnow);
		// nextTurnWorkers.retainAll(world.workers);

		// check if an existing free worker is next to cell
		processNeighbourWhileSome(command, snowNoWorker, freeWorker, nextTurnWorkers, 1);
		processNeighbourWhileSome(command, snowNoWorker, freeWorker, nextTurnWorkers, 2);
		processNeighbourWhileSome(command, snowNoWorker, freeWorker, nextTurnWorkers, 3);
		processNeighbourWhileSome(command, snowNoWorker, freeWorker, nextTurnWorkers, 4);

		// now proces worker with snow (no need to move):
		Iterator<CellW> itWork = freeWorker.iterator();
		while (itWork.hasNext()) {
			CellW worker = itWork.next();
			if (snowNoWorker.remove(worker)) {
				itWork.remove();
				nextTurnWorkers.add(worker);
			}
		}

		// remove neighbourg snow of already placed workers
		Collection<CellW> snowNeighbourWorker = new ArrayList<CellW>();
		for (CellW worker : nextTurnWorkers) {
			for (int dir = 0; dir < 4; dir++) {
				CellW dirCell = getCellInDir(worker, dir);
				if (snowNoWorker.remove(dirCell)) {
					snowNeighbourWorker.add(dirCell);
				}
			}
		}

		// int nbSnowToTarget = snowNoWorker.size();
		// if (nbSnowToTarget > 0) {
		// log("nbSnowToTarget=" + nbSnowToTarget);
		// }

		// 2nd loop for direction
		Collection<CellW> snowTargeted = new ArrayList<CellW>();
		// 1st the better associations
		targetSnowCell(command, snowNoWorker, freeWorker, nextTurnWorkers, snowTargeted, true);
		targetSnowCell(command, snowNoWorker, freeWorker, nextTurnWorkers, snowTargeted, true);
		// targetSnowCell(command, snowNoWorker, freeWorker, nextTurnWorkers, snowTargeted, true);
		// 2nd the other
		targetSnowCell(command, snowNoWorker, freeWorker, nextTurnWorkers, snowTargeted, false);

		if (freeWorker.size() > 0) {
			// random move for free workers
			// log("unoccupied workers " + freeWorker.size());
			Iterator<CellW> itFreeW = freeWorker.iterator();
			while (itFreeW.hasNext()) {
				CellW targetWorker = (CellW) itFreeW.next();
				itFreeW.remove();
				int theDir = targetWorker.lastDir;
				int refDistance = boardSize / 4;
				if (snowProba[targetWorker.r][targetWorker.c] > (BASE_SNOW_PROBABILITY / 2)) {
					// log("snowProba[targetWorker.r][targetWorker.c]=" + snowProba[targetWorker.r][targetWorker.c]);
					// refDistance = refDistance / 4;
					if (snowProba[targetWorker.r][targetWorker.c] > (BASE_SNOW_PROBABILITY)) {
						// refDistance = refDistance / 2;
						theDir = CellW.UNSET;
						// if (snowProba[targetWorker.r][targetWorker.c] > (BASE_SNOW_PROBABILITY * 2)) {
						// theDir = CellW.UNSET;
						// }
					}
				}
				if ((theDir == CellW.UNSET) || (rnd.nextInt(refDistance + 1) == 0) || isOnBorder(targetWorker)) {
					theDir = rnd.nextInt(4);
				}
				CellW dirCell = this.getCellInDir(targetWorker, theDir);
				// if (!isInBoard(dirCell) || nextTurnWorkers.contains(dirCell)) {
				// // then oposite dir
				// theDir = (theDir + 2) % 4;
				// dirCell = this.getCellInDir(targetWorker, theDir);
				// }
				if (isInBoard(dirCell) && !nextTurnWorkers.contains(dirCell)) {
					// if (isInBoard(dirCell)) {
					// new coordinates
					targetWorker.c = dirCell.c;
					targetWorker.r = dirCell.r;
					targetWorker.lastDir = theDir;
					command.add("M " + targetWorker.workerId + " " + Const.DIR_STR.charAt(theDir));
					nextTurnWorkers.add(targetWorker);
				} else {
					// can not move the worker
					targetWorker.lastDir = CellW.UNSET;
					nextTurnWorkers.add(targetWorker);
				}

			}
		}

		// should we add new worker ?
		int nbCurrentWorkers = world.workers.size();
		// check 1
		if (nextTurnWorkers.size() != nbCurrentWorkers) {
			logErr("1 bad check nextTurnWorkers.size()=" + nextTurnWorkers.size() + " != nbCurrentWorkers=" + nbCurrentWorkers);
		}

		// int averageSnowPerDay = snowFallSinceStart / (world.curDay + 1);
		// log("averageSnowPerDay=" + averageSnowPerDay);

		// do we need more workers ?
		// priority to snow4Borders
		final Collection<CellW> snowRemaining = new ArrayList<CellW>(snowNoWorker.size() + snow4Borders.size() + 30);
		// Collection<CellW> snowRemaining = new LinkedHashSet<CellW>(snowNoWorker.size() + snow4Borders.size());
		snowRemaining.addAll(snow4Borders);
		snowRemaining.addAll(snowNoWorker);
		// snowRemaining.addAll(snowNeighbourWorker);
		// snowRemaining.addAll(snowTargeted);
		if (world.curDay >= LAST_DAYS) {
			snowRemaining.addAll(snowNeighbourWorker);
			snowRemaining.addAll(snowTargeted);
		}

		// seems good with this order:
		// snowRemaining.addAll(snow4Borders);
		// snowRemaining.addAll(snowNeighbourWorker);
		// snowRemaining.addAll(snowNoWorker);

		snowNoWorker = null;
		while (snowRemaining.size() > 0 && nbCurrentWorkers < NB_MAX_WORKERS) {
			int costPerDay0 = calculateCostPerDay(nbCurrentWorkers);
			int costPerDay1 = calculateCostPerDay(nbCurrentWorkers + 1);
			// if (costPerDay1 < costPerDay0) {
			if (costPerDay1 < costPerDay0 || nbCurrentWorkers == 0) {
				CellW cell = snowRemaining.iterator().next();
				// add new worker
				world.addWorker(cell.r, cell.c);
				command.add("H " + cell.r + " " + cell.c);

				nbCurrentWorkers++;
				nextTurnWorkers.add(cell);
				snowRemaining.remove(cell);
				if (world.curDay < LAST_DAYS) {
					// remove also direct accessible cels but 1, 2 or 4 ?
					snowRemaining.remove(this.getCellInDir(cell, rnd.nextInt(4)));
				}

			} else {
				// log("no need for more workers " + nbCurrentWorkers);
				// break while
				break;
			}
		}
		// temporary call for test
		// calculateCostPerDay(nbCurrentWorkers);

		// }
		world.cleanAllSnow();
		world.updateTotalSalary();
		world.updateTotalFine();
		nbWorkersByDay += world.workers.size();

		// update probability keeping track of history
		// if (k > 0) {
		for (int row = 0; row < boardSize; row++) {
			for (int col = 0; col < boardSize; col++) {
				int before = snowProba[row][col];
				if (before > 0) {
					snowProba[row][col] = (before * 70) / 100;
				}
			}

		}
		// }
		for (int i = 0; i < k; i++) {
			int row = snowFalls[2 * i];
			int col = snowFalls[2 * i + 1];
			snowProba[row][col] = snowProba[row][col] + (BASE_SNOW_PROBABILITY / 2);
			CellW snowCell = new CellW(row, col);
			for (int dir = 0; dir < 4; dir++) {
				CellW dirCell = getCellInDir(snowCell, dir);
				if (isInBoard(dirCell)) {
					snowProba[dirCell.r][dirCell.c] = snowProba[dirCell.r][dirCell.c] + (BASE_SNOW_PROBABILITY / 8);
				}
			}
		}
		return command.toArray(new String[] {});
	}

	private int targetSnowCell(ArrayList<String> command, Set<CellW> snowNoWorker, final List<CellW> freeWorker,
			final Collection<CellW> nextTurnWorkers, Collection<CellW> snowTargeted, boolean testBetterDist) {
		int nbProcessed = 0;
		Iterator<CellW> itSnow = snowNoWorker.iterator();
		while (itSnow.hasNext()) {
			CellW snowCell = itSnow.next();
			if (freeWorker.isEmpty()) {
				// there are no more free worker
				break;
			}

			// is there any snow to clean not so far for the free worker ?

			int theDir = 0;
			// we should chose the closer cell
			CellW targetWorker = calculateBestTarget(snowCell, freeWorker);
			// to check algorithm
			int dist1 = distance(snowCell, targetWorker);

			if (testBetterDist) {
				CellW bestSnowForThisWorker = calculateBestTarget(targetWorker, snowNoWorker);
				if (distance(targetWorker, bestSnowForThisWorker) < dist1) {
					// log("There is a better association " + (dist1 - distance(targetWorker, bestSnowForThisWorker)));
					// go to next snow cell
					continue;
				}
			}

			CellW targetWorkerAlready = calculateBestTarget(snowCell, nextTurnWorkers);
			if (targetWorkerAlready != null) {
				int distAlready = distance(snowCell, targetWorkerAlready);
				if ((dist1 - distAlready) > MAX_DIFFERENCE) {
					// not a valuable target
					// log("diff already=" + (dist1 - distAlready));
					// go to next snow cell
					continue;
				}
			}

			theDir = getDirFromCellToCell2(targetWorker, snowCell);
			// theDir = getDirFromCellToCellRandom(targetWorker, snowCell);
			CellW dirCell = getCellInDir(targetWorker, theDir);
			// if cell is free for next turn, else there is already a better worker for the target
			if (!nextTurnWorkers.contains(dirCell)) {

				// should we remove the target ?
				if (dist1 < MAX_DIST) {
					// snowNoWorker.remove(snowCell);
					itSnow.remove();
					snowTargeted.add(snowCell);
				}

				freeWorker.remove(targetWorker);
				// new coordinates
				targetWorker.c = dirCell.c;
				targetWorker.r = dirCell.r;
				if (!(dist1 - 1 == distance(snowCell, targetWorker))) {
					logErr("dist1=" + dist1 + " not better");
				}
				command.add("M " + targetWorker.workerId + " " + Const.DIR_STR.charAt(theDir));
				nextTurnWorkers.add(targetWorker);
				nbProcessed++;
			}
			// else {
			// log("cell is not free for next turn");
			// }

		}
		return nbProcessed;
	}

	private void initMinMax(List<CellW> workers) {
		if (workers.isEmpty()) {
			minPos.c = 0;
			minPos.r = 0;
			maxPos.c = boardSize - 1;
			maxPos.r = boardSize - 1;

		} else {
			minPos.c = Integer.MAX_VALUE;
			minPos.r = Integer.MAX_VALUE;
			maxPos.c = 0;
			maxPos.r = 0;
			minPos2.c = Integer.MAX_VALUE;
			for (CellW worker : workers) {
				if (worker.c < minPos.c) {
					minPos.c = worker.c;
				}
				if (worker.r < minPos.r) {
					minPos.r = worker.r;
				}
				if (worker.c > maxPos.c) {
					maxPos.c = worker.c;
				}
				if (worker.r > maxPos.r) {
					maxPos.r = worker.r;
				}
				// angles
				if (worker.c + worker.r < minPos2.c) {
					minPos2.c = worker.c + worker.r;
				}
			}
		}
	}

	private boolean isInsideWorkerSquare(CellW newPos) {
		return newPos.c >= minPos.c && newPos.c <= maxPos.c && newPos.r >= minPos.r && newPos.r <= maxPos.r
		// && (newPos.c + newPos.r >= minPos2.c)
		// return newPos.c > minPos.c && newPos.c < maxPos.c && newPos.r > minPos.r && newPos.r < maxPos.r
		;
	}

	/** Extract snow completly inside not to be targeted. */
	private Set<CellW> getSnow4Borders(Set<CellW> snowNoWorker) {
		Set<CellW> snow4Borders = new HashSet<CellW>(snowNoWorker.size() / 2);
		for (CellW snowCell : snowNoWorker) {
			boolean allBorder = true;
			int nbBorders = 0;
			for (int dir = 0; dir < 4; dir++) {
				CellW dirCell = getCellInDir(snowCell, dir);
				if (snowNoWorker.contains(dirCell)) {
					// OK
					nbBorders++;
				} else {
					if (isInsideWorkerSquare(dirCell)) {
						allBorder = false;
					}
					// for dir
					// break;
				}

			}
			if (allBorder) {
				if (nbBorders >= 3) {
					snow4Borders.add(snowCell);
				}
			}
		}
		return snow4Borders;
	}

	/** process snow with determinu number of snow while there is snow in this case. */
	private void processNeighbourWhileSome(Collection<String> command, final Set<CellW> snowNoWorker, final List<CellW> freeWorker,
			final Collection<CellW> nextTurnWorkers, int nbNeighbourg) {
		int nbProcessed = 1;
		while (nbProcessed != 0) {
			nbProcessed = processNeighbourCells(command, snowNoWorker, freeWorker, nextTurnWorkers, nbNeighbourg);
		}
	}

	private int processNeighbourCells(Collection<String> command, final Set<CellW> snowNoWorker, final List<CellW> freeWorker,
			final Collection<CellW> nextTurnWorkers, final int nbNeighboursToFind) {
		int nbProcessed = 0;
		// if (freeWorker.isEmpty()) {
		// return 0;
		// }

		// calculate nb neighbours (snow in snow)
		// for (CellW snowCell : snowNoWorker) {
		// snowCell.nbNeighbours = 0;
		// for (int dir = 0; dir < 4; dir++) {
		// CellW dirCell = getCellInDir(snowCell, dir);
		// if (snowNoWorker.contains(dirCell)) {
		// snowCell.nbNeighbours++;
		// }
		//
		// }
		// }

		// sort
		// Collection<CellW> snowPriorise = new TreeSet<CellW>(new Comparator<CellW>() {
		// public int compare(CellW o1, CellW o2) {
		// if (o1.nbNeighbours < o2.nbNeighbours) {
		// return -1;
		// } else if (o1.nbNeighbours > o2.nbNeighbours) {
		// return +1;
		// }
		// // no equal, we want only to sort
		// return +1;
		// }
		// });
		// snowPriorise.addAll(snowNoWorker);
		// if (snowPriorise.size() != snowNoWorker.size()) {
		// logErr("snowPriorise.size() != snowNoWorker.size()" + snowPriorise.size() + " " + snowNoWorker.size());
		// }

		// Iterator<CellW> itSnow = snowPriorise.iterator();
		Iterator<CellW> itSnow = snowNoWorker.iterator();
		while (itSnow.hasNext()) {
			CellW snowCell = itSnow.next();

			// not to always go in the same direction
			int biasDir = rnd.nextInt(4);

			CellW dirCellFound = null;
			int nbNeighbours = 0;

			// check one of the 4 next cells to be cleaned
			for (int dir = 0; dir < 4; dir++) {
				int dirModified = (dir + biasDir) % 4;
				CellW dirCell = getCellInDir(snowCell, dirModified);
				if (freeWorker.contains(dirCell)) {
					dirCell.lastDir = dirModified;
					dirCellFound = dirCell;
					nbNeighbours++;
				}

			}
			// if number on neighbours is the one requested
			if (nbNeighbours == nbNeighboursToFind) {
				// this worker is no more free
				int indexOfWorker = freeWorker.indexOf(dirCellFound);
				CellW worker = freeWorker.get(indexOfWorker);
				// CellW worker = freeWorker.tailSet(dirCellFound).iterator().next();
				freeWorker.remove(indexOfWorker);
				// the cell is going to be cleaned
				itSnow.remove();
				// snowNoWorker.remove(snowCell);

				// new coordinates
				worker.c = snowCell.c;
				worker.r = snowCell.r;
				// +2 means +180°
				int dirOposite = (dirCellFound.lastDir + 2) % 4;

				command.add("M " + worker.workerId + " " + Const.DIR_STR.charAt(dirOposite));
				nextTurnWorkers.add(worker);
				nbProcessed++;

			}

			if (freeWorker.isEmpty()) {
				// there are no more free worker
				break;
			}

		}
		return nbProcessed;
	}

	private boolean isOnBorder(CellW newPos) {
		int border = boardSize - 1;
		return newPos.c == 0 || newPos.c == border || newPos.r == 0 || newPos.r == border;
	}

	private boolean isInBoard(CellW newPos) {
		return newPos.c >= 0 && newPos.c < boardSize && newPos.r >= 0 && newPos.r < boardSize;
	}

	private int getDirFromCellToCell2(CellW cellFrom, CellW toCell) {
		int theDir = 0;
		if (Math.abs(toCell.r - cellFrom.r) > Math.abs(toCell.c - cellFrom.c)) {
			if (toCell.r > cellFrom.r) {
				theDir = 0;
			} else {
				theDir = 2;
			}
		} else {
			if (toCell.c < cellFrom.c) {
				theDir = 1;
			} else {
				theDir = 3;
			}
		}
		return theDir;
	}

	private int getDirFromCellToCellRandom(CellW cellFrom, CellW toCell) {
		int distanceBefore = distance(cellFrom, toCell);
		final int biasDir = 0;// rnd.nextInt(4);
		// check one of the 4 next cells to be cleaned
		for (int dir = 0; dir < 4; dir++) {
			int dirModified = (dir + biasDir) % 4;
			CellW dirCell = getCellInDir(cellFrom, dirModified);
			if (distance(dirCell, toCell) < distanceBefore) {
				return dirModified;
			}
		}

		logErr("No direction found!");
		return -1;
	}

	private int calculateCostPerDay(int nbCurrentWorkers) {
		if (world.curDay == 0) {
			return (1 - nbCurrentWorkers) * (1 - nbCurrentWorkers);
		} else if (nbWorkersByDay <= 100) {
			// 100 is empiric
			// return (1 - nbCurrentWorkers) * (1 - nbCurrentWorkers);
			return calculateCostPerDayBasic(nbCurrentWorkers);
		}
		int remainingDays = Const.SIMULATION_TIME - world.curDay;

		double curDay = world.curDay;
		double inefficace = world.totFine * (nbWorkersByDay / curDay) / curDay;
		// log("world.curDay=" + world.curDay + "  inefficace=" + inefficace + "  nbCurrentWorkers=" +
		// nbCurrentWorkers);
		int fineTotalCost = world.totFine + (int) (inefficace / (double) nbCurrentWorkers * (double) remainingDays);

		// consider fines that will be regularised by this turn new workers
		fineTotalCost = fineTotalCost - (nbCurrentWorkers - nbWorkersBeforeTurn) * snowFine;

		int salaryCost = world.totSalary + (nbCurrentWorkers * remainingDays * salary);
		int totalCost = fineTotalCost + salaryCost;
		// log("salaryCost=" + salaryCost + "  fineTotalCost=" + fineTotalCost + "  totalCost=" + totalCost);
		return totalCost;
	}

	private int calculateCostPerDayBasic(int nbCurrentWorkers) {
		// assumption on 6 or 15 days ? 8 is good
		int nbDays = 10;
		int fineCost = world.snowCnt - nbDays * nbCurrentWorkers / 2;
		if (fineCost < 0) {
			fineCost = 0;
		}
		return nbCurrentWorkers * salary + fineCost * snowFine;
	}

	private void log(String message) {
		System.out.println(message);
	}

	private void logErr(String message) {
		System.err.println(message);
	}

	private CellW calculateBestTarget(CellW worker, Collection<CellW> snowNoWorker) {
		CellW bestTarget = null;
		Iterator<CellW> it = snowNoWorker.iterator();
		int closestDist = Integer.MAX_VALUE;
		int i = 0;
		while (it.hasNext() && (i < MAX_BEST_TARGET_EVAL)) {
			i++;
			CellW cell = (CellW) it.next();
			int dist = distance(worker, cell);
			if (dist < closestDist) {
				bestTarget = cell;
				closestDist = dist;
			}
		}
		// log("closestDist=" + closestDist);
		return bestTarget;
	}

	private int distance(CellW worker, CellW bestTarget) {
		return Math.abs(worker.c - bestTarget.c) + Math.abs(worker.r - bestTarget.r);
	}

	private CellW getCellInDir(CellW base, int dir) {
		CellW newDir = new CellW(base.r + Const.DR[dir], base.c + Const.DC[dir]);
		return newDir;
	}

}

class Const {

	public static final int SIMULATION_TIME = 2000;
	/** 100. */
	public static final int MAX_WORKERS = 100;
	public static final String DIR_STR = "DLUR";
	public static final int[] DR = new int[] { 1, 0, -1, 0 };
	public static final int[] DC = new int[] { 0, -1, 0, 1 };

}

class Board {

	final Object workersLock = new Object();

	/** number of cells with snow. */
	public int snowCnt;
	boolean[][] haveSnow;

	/** Optimized list of cells. */
	public Collection<CellW> cellsWithSnow = new HashSet<CellW>(100);

	public List<CellW> workers = new ArrayList<CellW>();
	Set<Integer> usedWorkers = new HashSet<Integer>();

	int salary, fine;
	int totSalary, totFine;
	public int curDay = -1;

	public Board(int boardSize, int salary, int fine) {
		this.salary = salary;
		this.fine = fine;
		haveSnow = new boolean[boardSize][boardSize];
	}

	public void updateTotalSalary() {
		synchronized (workersLock) {
			totSalary += salary * workers.size();
		}
	}

	public void updateTotalFine() {
		totFine += snowCnt * fine;
	}

	public void addSnow(int r, int c) {
		cellsWithSnow.add(new CellW(r, c));
		if (!haveSnow[r][c]) {
			snowCnt++;
			haveSnow[r][c] = true;
		}
	}

	public void removeSnow(int r, int c) {
		if (haveSnow[r][c]) {
			snowCnt--;
			haveSnow[r][c] = false;
		}
	}

	public void startNewDay() {
		curDay++;
		usedWorkers.clear();
	}

	public String addWorker(int r, int c) {
		synchronized (workersLock) {
			if (workers.size() == Const.MAX_WORKERS) {
				return "You are allowed to have at most " + Const.MAX_WORKERS + " workers.";
			} else if (r < 0 || r >= haveSnow.length || c < 0 || c >= haveSnow.length) {
				return "You are trying to hire a worker at a cell outside the board.";
			} else {
				CellW newWorker = new CellW(r, c);
				// set the unique ID
				newWorker.workerId = workers.size();
				workers.add(newWorker);
				usedWorkers.add(workers.size() - 1);
				removeSnow(r, c);
				return "";
			}
		}
	}

	public String moveWorker(int id, int dir) {
		synchronized (workersLock) {
			if (id < 0 || id >= workers.size()) {
				return "You are trying to move worker which does not exist.";
			} else if (usedWorkers.contains(id)) {
				return "You are trying to execute a command for some worker more than once during the same turn.";
			} else {
				CellW worker = workers.get(id);
				worker.r += Const.DR[dir];
				worker.c += Const.DC[dir];
				if (worker.r < 0 || worker.c < 0 || worker.r >= haveSnow.length || worker.c >= haveSnow.length) {
					return "You are trying to move a worker outside the board.";
				}
				removeSnow(worker.r, worker.c);
				usedWorkers.add(id);
				return "";
			}
		}
	}

	public void cleanAllSnow() {
		synchronized (workersLock) {
			for (CellW worker : workers) {
				removeSnow(worker.r, worker.c);
				// remove the worker cell.
				cellsWithSnow.remove(worker);
			}
		}
	}

}

/** Cell and Worker. */
class CellW implements Comparable<CellW> {

	public final static int UNSET = -1;

	public int r, c;

	public int workerId = UNSET;
	/** number of neighbours with snow. */
	public int nbNeighbours = UNSET;

	/** last direction in a random move. */
	public int lastDir = UNSET;

	public CellW(int r, int c) {
		this.r = r;
		this.c = c;
	}

	public boolean equals(Object other) {
		if (!(other instanceof CellW)) {
			return false;
		}

		CellW otherCell = (CellW) other;
		return this.r == otherCell.r && this.c == otherCell.c;
	}

	public int hashCode() {
		return 100 * r + c;
	}

	public int compareTo(CellW other) {
		return (r == other.r ? c - other.c : r - other.r);
	}

	@Override
	public String toString() {
		if (workerId == UNSET) {
			return "CellW [r=" + r + ", c=" + c + "]";

		} else {
			return "CellW [r=" + r + ", c=" + c + ", workerId=" + workerId + "]";

		}
	}

}